package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 滑动窗口<br>
 * 哈希表、字符串、滑动窗口<br>
 * 中等
 *
 * <h1>3. 无重复字符的最长子串</h1>
 *
 * <p>给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。</p>
 */
public class C08LengthOfLongestSubstring {
    public static void main(String[] args) {
        C08LengthOfLongestSubstring lengthOfLongestSubstring = new C08LengthOfLongestSubstring();

        String s = "tmmzuxt";
        TimeCostUtil.timeCost("滑动窗口", () -> lengthOfLongestSubstring.solution1(s));
        TimeCostUtil.timeCost("滑动窗口_我的方法", () -> lengthOfLongestSubstring.solution1_mine(s));

        String str = DataGeneratorUtil.generateRandomString(10000000);
        TimeCostUtil.timeCost("滑动窗口", () -> lengthOfLongestSubstring.solution1(str));
        TimeCostUtil.timeCost("滑动窗口", () -> lengthOfLongestSubstring.solution1_1(str));
        TimeCostUtil.timeCost("滑动窗口_我的方法", () -> lengthOfLongestSubstring.solution1_mine(str));

    }

    public int solution1_mine(String s) {
        Map<Character, Integer> map = new HashMap<>();
        // 滑动窗口大小
        int max = 0;
        // 滑动窗口左右边界
        int l = 0, r = 0;
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                // 如果集合中不包含当前字符，则加入集合
                map.put(s.charAt(i), i);
                // 滑动窗口右边界++
                r++;
                // 计算最大值
                max = Math.max(max, r - l);
            } else {
                // 如果集合中包含当前字符，则将左边界移到集合中与当前字符相同的字符的右边界，并移除集合中相同的字符
                // 删除集合中重复元素及其之前索引的元素
                // 确定集合中和当前索引相同的元素
                char c = s.charAt(i);
                // 确定集合中要删除到的索引
                int toDelIndex = map.get(c) + 1;
                while (l < toDelIndex) {
                    // 删除集合中重复元素及其之前索引的元素
                    map.remove(s.charAt(l));
                    // 滑动窗口左边界++
                    l++;
                }
                // 集合中加入当前字符
                map.put(s.charAt(i), i);
                // 滑动窗口右边界++
                r++;
            }

        }
        return max;
    }

    // 滑动窗口
    public int solution1(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    public int solution1_1(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }

    public int solution1_2(String s) {
        int max = 0;
        int[] count = new int[128];
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
            while (count[s.charAt(i)] > 1) {
                count[s.charAt(left)]--;
                left++;
            }
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}
